#![allow(dead_code)]
use crate::compr::{random_array, random_i32, random_idx};
use std::cmp;

use std::cmp::Reverse;
use std::collections::BinaryHeap;

fn swap(arr: &mut Vec<i32>, i: usize, j: usize) {
    if j == i {
        return;
    }
    let tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

fn comparetor(fn1: &dyn Fn(&mut Vec<i32>) -> &mut Vec<i32>) -> bool {
    for _ in 0..1000 {
        let mut v1 = random_array(20, 0..101);
        let mut v2 = v1.clone();
        v1.sort();
        let v2 = fn1(&mut v2);

        for i in 0..v1.len() {
            if v1[i] != v2[i] {
                return false;
            }
        }
    }
    true
}

/******************************
- 选择排序算法流程
  - 在[0, n-1]找到最小值a[i]
  - swap(a, 0, i)
  - 在[1, n-1]找最小值a[i]
  - swap(a, 1, i)
*******************************/
fn choice_sort(arr: &mut Vec<i32>) -> &mut Vec<i32> {
    for i in 0..arr.len() - 1 {
        let mut min_idx = i;
        for j in i + 1..arr.len() {
            min_idx = if arr[j] < arr[min_idx] { j } else { min_idx };
        }
        swap(arr, i, min_idx);
    }

    arr
}

/* 冒泡排序
- [0, N-1]
    - 比较a[i], a[i+1]，谁大谁往右移
    - 一轮之后a[N-1]是最大值
- [0, N-2]
    - 得到a[N-2]是最大值
*/
fn bubble_sort(arr: &mut Vec<i32>) -> &mut Vec<i32> {
    if arr.len() < 2 {
        return arr;
    }
    for sorted_idx in (0..arr.len()).rev() {
        for i in 0..sorted_idx {
            if arr[i] > arr[i + 1] {
                swap(arr, i, i + 1);
            }
        }
    }
    arr
}

fn find_orr(arr: &Vec<i32>) -> i32 {
    let mut eor = 0;
    for cur in arr.iter() {
        eor ^= cur;
    }
    eor
}

fn find2num(arr: &Vec<i32>) -> (i32, i32) {
    let mut eor = 0; // eor = a ^ b
    let mut eor2 = 0; // eor2 = a or b
    for cur in arr.iter() {
        eor ^= cur;
    }

    let right_one = eor & (!eor + 1); // 取出最右位的1
    for cur in arr.iter() {
        if cur & right_one != 0 {
            eor2 ^= cur;
        }
    }

    let a = eor ^ eor2;
    let b = eor ^ a;
    (a, b)
}

/* 插入排序
i = [0, arr.len())，实现i左边都有序；
  - 先实现[0, 0]范围内有序 (ok)
  - 实现[0, 1]范围有序, i = 1
    - 向左看
      - 如果i比左边小，就交换
    - 再向左看，直到
      - a[i] > a[i-1] 或者 i 越界
*/

fn insert_sort(arr: &mut Vec<i32>) -> &mut Vec<i32> {
    if arr.len() < 2 {
        return arr;
    }
    for i in 0..arr.len() {
        for j in (1..=i).rev() {
            if arr[j] < arr[j - 1] {
                swap(arr, j, j - 1);
            }
        }
    }
    arr
}

pub fn test_bubble_sort() {
    let r = comparetor(&bubble_sort);
    println!("r: {}", r);
}

pub fn test_insert_sort() {
    let r = comparetor(&insert_sort);
    println!("r: {}", r);
}

fn bin_searchmax(arr: &Vec<i32>, l: usize, r: usize) -> i32 {
    if l == r {
        return arr[l];
    };
    let mid = l + ((r - l) >> 1);
    let left_max = bin_searchmax(arr, l, mid);
    let right_max = bin_searchmax(arr, mid + 1, r);
    return cmp::max(left_max, right_max);
}

pub fn test_bin_searchmax(times: usize) {
    for _ in 0..times {
        let arr = random_array(100, 0..101);
        let my_max = bin_searchmax(&arr, 0, arr.len() - 1);
        let mut arr = arr;
        arr.sort();
        let system_max = arr[arr.len() - 1 as usize];
        if my_max != system_max {
            println!("false");
        }
    }
    println!("true");
}

fn merge_arr(left_arr: Vec<i32>, right_arr: Vec<i32>) -> Vec<i32> {
    let mut i = 0usize;
    let mut j = 0usize;
    let capacity = left_arr.len() + right_arr.len();
    let mut res: Vec<i32> = Vec::with_capacity(capacity);
    while i < left_arr.len() && j < right_arr.len() {
        if left_arr[i] <= right_arr[j] {
            res.push(left_arr[i]);
            i += 1;
        } else {
            res.push(right_arr[j]);
            j += 1;
        }
    }
    res.extend_from_slice(&left_arr[i..]);
    res.extend_from_slice(&right_arr[j..]);
    res
}

fn merge_sort(arr: Vec<i32>) -> Vec<i32> {
    if arr.len() < 2 {
        return arr;
    }
    let mid_plus = (arr.len() + 1) / 2;
    let mut left_arr = arr;
    let right_arr = left_arr.split_off(mid_plus);
    let left_arr = merge_sort(left_arr);
    let right_arr = merge_sort(right_arr);
    return merge_arr(left_arr, right_arr);
}

fn comparetor2<F>(fn1: F) -> bool
where
    F: Fn(Vec<i32>) -> Vec<i32>,
{
    for _ in 0..1000 {
        let mut system_sort = vec![2, 3, 1, 5, 6, 2];
        let my_sort = system_sort.clone();
        system_sort.sort();
        let my_sort = fn1(my_sort);

        for i in 0..system_sort.len() {
            if my_sort[i] != system_sort[i] {
                return false;
            }
        }
    }
    true
}

pub fn test_merge_sort() {
    let r = comparetor2(merge_sort);
    println!("test_merge_sort: {}", r);
}

fn smallsum_merge(left_arr: Vec<i32>, right_arr: Vec<i32>) -> (i32, Vec<i32>) {
    let mut ss = 0;
    let mut i = 0;
    let mut j = 0;
    let mut merge: Vec<i32> = Vec::new();
    while i < left_arr.len() && j < right_arr.len() {
        if left_arr[i] < right_arr[j] {
            ss += left_arr[i] * (right_arr.len() - j) as i32;
            merge.push(left_arr[i]);
            i += 1;
        } else {
            merge.push(right_arr[j]);
            j += 1;
        }
    }
    merge.extend_from_slice(&left_arr[i..]);
    merge.extend_from_slice(&right_arr[j..]);
    (ss, merge)
}

fn smallsum_process(arr: Vec<i32>) -> (i32, Vec<i32>) {
    if arr.len() == 1 {
        return (0, arr);
    }
    let mid_plus: usize = (arr.len() + 1) / 2;
    let mut left_arr = arr;
    let right_arr = left_arr.split_off(mid_plus);
    let (ss_left, left_arr) = smallsum_process(left_arr);
    let (ss_right, right_arr) = smallsum_process(right_arr);
    let (ss_merge, merge) = smallsum_merge(left_arr, right_arr);
    return (ss_left + ss_right + ss_merge, merge);
}

fn smallsum(arr: Vec<i32>) -> i32 {
    let mut ss = 0;
    for j in (0..arr.len()).rev() {
        for i in 0..j {
            if arr[i] < arr[j] {
                ss += arr[i];
            }
        }
    }
    ss
}

pub fn test_smallsum(times: usize) -> bool {
    for _ in 0..times {
        let v1 = vec![2, 3, 1, 5, 6, 2];
        let v2 = v1.clone();
        let (ss1, _) = smallsum_process(v1);
        let ss2 = smallsum(v2);
        if ss1 != ss2 {
            println!("test_smallsum: false");
            return false;
        }
    }
    println!("test_smallsum: true");
    true
}

fn split2part(arr: &mut Vec<i32>, num: i32) {
    let mut edge: usize = 0;
    let mut i = 0usize;
    while i < arr.len() {
        if arr[i] <= num {
            swap(arr, i, edge);
            edge += 1;
        }
        i += 1;
    }
}

fn split3part(arr: &mut Vec<i32>, num: i32) {
    let mut small = 0usize;
    let mut big = arr.len();
    let mut i = 0usize;
    while i < big {
        if arr[i] < num {
            arr.swap(i, small);
            small += 1;
            i += 1;
        } else if arr[i] > num {
            big -= 1;
            arr.swap(i, big);
        } else {
            i += 1;
        }
    }
}

fn quick_sort1(mut arr: Vec<i32>) -> Vec<i32> {
    if arr.len() <= 1 {
        return arr;
    }
    let last_idx = arr.len() - 1;
    let num = arr[last_idx];
    let mut small = 0usize;
    let mut i = 0usize;
    while i < last_idx {
        if arr[i] <= num {
            swap(&mut arr, i, small);
            small += 1;
        }
        i += 1;
    }
    swap(&mut arr, small, last_idx);

    let right_arr = arr.drain(small + 1..).collect();
    let left_arr = arr.drain(0..small).collect();
    let left_sorted = quick_sort1(left_arr);
    let right_sorted = quick_sort1(right_arr);
    [left_sorted, right_sorted].join(&num)
}

fn quick_sort2(mut arr: Vec<i32>) -> Vec<i32> {
    if arr.len() <= 1 {
        return arr;
    }
    let mut outline = false;
    let mut i = 0usize;
    let last = arr.len() - 1;
    let mut small = 0usize; // [0, small-1]是<num的区域
    let mut big = last - 1; // [big+1, end]是>num的区域
    while i <= big {
        if arr[i] < arr[last] {
            arr.swap(i, small);
            small += 1;
            i += 1;
        } else if arr[i] > arr[last] {
            arr.swap(i, big);
            //rust的usize>= 0
            if big == 0 {
                outline = true;
                break;
            } else {
                big -= 1;
            }
        } else {
            i += 1;
        }
    }
    if outline {
        // >num区的第1个数在0位置时，要单独处理
        arr.swap(i, last);
        big = 0;
    } else {
        // 把最后一个数和>num区的第1个数交换
        arr.swap(big + 1, last);
        // >num边界同时向右移
        big += 1; // 保证big_plus是>num的区域 [big+1, end]
    }

    // arr => [small_arr, equal_arr, big_arr]
    let big_arr = arr.drain(big + 1..).collect();
    let small_arr = arr.drain(0..small).collect();
    let big_sorted = quick_sort2(big_arr);
    let small_sorted = quick_sort2(small_arr);
    [small_sorted, big_sorted].join(&arr[..])
}

fn quick_sort3(mut arr: Vec<i32>) -> Vec<i32> {
    if arr.len() <= 1 {
        return arr;
    }
    let last = arr.len() - 1;
    let idx = random_idx(arr.len());
    arr.swap(idx, last);
    quick_sort2(arr)
}

pub fn test_quicksort(times: usize) -> bool {
    for _ in 0..times {
        let arr = random_array(100, 0..101);
        let arr2 = arr.clone();
        let arr3 = arr.clone();
        let arr_bkp = arr.clone();

        let arr_sorted1 = quick_sort1(arr);
        let arr_sorted2 = quick_sort2(arr2);
        let arr_sorted3 = quick_sort3(arr3);
        for i in 0..arr_sorted1.len() {
            if arr_sorted1[i] != arr_sorted2[i] {
                println!("test_quicksort: failed!");
                println!("arr: {:?}", arr_bkp);
                return false;
            }
            if arr_sorted1[i] != arr_sorted3[i] {
                println!("test_quicksort: failed!");
                println!("arr: {:?}", arr_bkp);
                return false;
            }
        }
    }
    println!("test_quicksort: success!");
    true
}

pub fn test_splitpart() {
    let num = 0;
    let mut arr = random_array(10, -100..101);
    let mut arr2 = arr.clone();
    println!("用{}把数组分成<=和>{}两部分(不排序)：", num, num);
    split2part(&mut arr, num);
    println!("split2part: {:?}", arr);
    split3part(&mut arr2, num);
    println!("split3part: {:?}", arr2);
}

fn heap_insert(arr: &mut Vec<i32>, num: i32) {
    arr.push(num);
    let mut i = arr.len() - 1;
    if i == 0 {
        return;
    }
    while i > 0 && arr[i] > arr[(i - 1) / 2] {
        arr.swap(i, (i - 1) / 2);
        i = (i - 1) / 2;
    }
}

fn heapify(arr: &mut Vec<i32>, idx: usize, heapsize: usize) {
    let mut i = idx;
    let mut left = 2 * i + 1;

    while left < heapsize {
        let right = left + 1;
        let max_idx = if right < heapsize && arr[left] < arr[right] {
            right
        } else {
            left
        };

        let max_idx = if arr[i] < arr[max_idx] { max_idx } else { i };
        if max_idx == i {
            break;
        }
        arr.swap(i, max_idx);
        i = max_idx;
        left = 2 * i + 1;
    }
}

fn heap_sort(arr: Vec<i32>) -> Vec<i32> {
    let mut res: Vec<i32> = Vec::new();
    for num in arr {
        heap_insert(&mut res, num);
    }

    let mut heapsize = res.len();
    while heapsize > 0 {
        res.swap(0, heapsize - 1);
        heapsize -= 1;
        heapify(&mut res, 0, heapsize);
    }

    res
}

pub fn test_heap_sort(times: usize) {
    for _ in 0..times {
        let mut arr1 = random_array(100, 0..101);
        let arr2 = arr1.clone();
        let bkp = arr2.clone();
        arr1.sort();
        let sorted = heap_sort(arr2);
        for i in 0..arr1.len() {
            if arr1[i] != sorted[i] {
                println!("堆排序测试失败!\n");
                println!("测试数组：{:?}", bkp);
                return;
            }
        }
    }
    println!("堆排序测试成功!");
}

fn sortarr_distancek(arr: Vec<i32>, k: usize) -> Vec<i32> {
    let mut min_heap = BinaryHeap::new();
    let mut res: Vec<i32> = vec![];

    for i in 0..k {
        min_heap.push(Reverse(arr[i]));
    }
    for i in k..arr.len() {
        if let Some(Reverse(min_val)) = min_heap.pop() {
            res.push(min_val);
        }
        min_heap.push(Reverse(arr[i]));
    }
    while let Some(Reverse(min_val)) = min_heap.pop() {
        res.push(min_val);
    }

    res
}

fn get_digit(num: i32, d: usize) -> usize {
    let mut num = num;
    for _ in 0..d {
        num /= 10;
    }
    (num % 10) as usize
}

fn test_get_digit() {
    let sample = random_i32(0, 1000000);
    println!("num: {}", sample);
    for d in 0..7 {
        let n = get_digit(sample, d);
        println!("第{}位: {}", d, n);
    }
}

fn get_ndigit(arr: &Vec<i32>) -> usize {
    let mut max = arr[0];
    for &num in arr.iter() {
        max = if max < num { num } else { max }
    }
    let mut ndigit = 0;
    while max > 0 {
        max /= 10;
        ndigit += 1;
    }
    ndigit
}

fn radix_sort(arr: Vec<i32>, ndigit: usize) -> Vec<i32> {
    let mut arr = arr;
    let mut buckets: Vec<Vec<i32>> = vec![vec![]; 10];

    for d in 0..ndigit {
        for i in 0..arr.len() {
            let dnum = get_digit(arr[i], d);
            buckets[dnum].push(arr[i]);
        }
        let mut i = 0usize;
        for bucket in buckets.iter_mut() {
            for &num in bucket.iter() {
                arr[i] = num;
                i += 1;
            }
            bucket.clear();
        }
    }
    arr
}

fn radix_sort2(arr: Vec<i32>, ndigit: usize) -> Vec<i32> {
    let mut arr = arr;
    let mut help = vec![0; arr.len()];
    for digit in 0..ndigit {
        // 词频
        let mut count: Vec<usize> = vec![0; 10];
        for &num in arr.iter() {
            count[get_digit(num, digit)] += 1;
        }
        // 前缀和
        for i in 1..count.len() {
            count[i] += count[i - 1];
        }
        for i in (0..arr.len()).rev() {
            let idx = get_digit(arr[i], digit);
            help[count[idx] - 1] = arr[i];
            count[idx] -= 1;
        }
        for i in 0..help.len() {
            arr[i] = help[i];
        }
    }

    arr
}

pub fn test_radix_sort(times: usize) {
    for _ in 0..times {
        let arr1 = random_array(10, 0..10000);
        let arr2 = arr1.clone();
        let bkp = arr1.clone();
        let ndigit = get_ndigit(&arr1);
        let sorted1 = radix_sort(arr1, ndigit);
        let sorted2 = radix_sort2(arr2, ndigit);
        for i in 0..bkp.len() {
            if sorted1[i] != sorted2[i] {
                println!("基数桶排序失败");
                println!("arr: {:?}", bkp);
            }
        }
    }
    println!("基数桶排序成功");
}

fn split_oddeven_quick(arr: &mut Vec<i32>) {
    let mut odd = 0usize;
    let mut i = 0usize;
    while i < arr.len() {
        if arr[i] % 2 == 0 {
            arr.swap(i, odd);
            odd += 1;
        }
        i += 1;
    }
}

pub fn test_quick_oddeven() {
    let mut arr = random_array(10, 0..21);
    println!("arr: {:?}", arr);
    split_oddeven_quick(&mut arr);
    println!("split odd even: {:?}", arr);
}

fn merge_oddeven_arr(
    left: Vec<i32>,
    edgel: usize,
    right: Vec<i32>,
    edger: usize,
) -> (usize, Vec<i32>) {
    let mut res = vec![];

    res.extend_from_slice(&left[..edgel]);
    res.extend_from_slice(&right[..edger]);
    res.extend_from_slice(&left[edgel..]);
    res.extend_from_slice(&right[edger..]);

    (edgel + edger, res)
}

fn merge_oddeven(arr: Vec<i32>) -> (usize, Vec<i32>) {
    if arr.len() == 1 {
        let edge = if arr[0] % 2 != 0 { 0 } else { 1 };
        return (edge, arr);
    }
    let mid_plus = (arr.len() + 1) / 2;
    let mut left = arr;
    let right = left.split_off(mid_plus);
    let (edge_l, left) = merge_oddeven(left);
    let (edge_r, right) = merge_oddeven(right);
    merge_oddeven_arr(left, edge_l, right, edge_r)
}

pub fn test_merge_oddeven() {
    let arr = random_array(10, 0..101);
    println!("数组:{:?}", arr);
    let (edge, oddeven) = merge_oddeven(arr);
    println!("奇偶分开: {:?}, 边界: {}", oddeven, oddeven[edge]);
}
